package leetcode.editor.cn;

//[121]买卖股票的最佳时机
public class BestTimeToBuyAndSellStock121 {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStock121().new Solution();
        //solution.maxProfit(new int[]{7,1,5,3,6,4});
        solution.maxProfit(new int[]{7, 6, 4, 3, 1});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //思路：
        //寻找。左边最小值。
        //maxProfit = 当前值 - 最小值。
        public int maxProfitFindLeftMin(int[] prices) {
            int maxProfit =0;
            if (prices == null || prices.length<1) {
                return maxProfit;
            }
            int leftMin = prices[0];
            for (int i = 0; i < prices.length; i++) {
                int price = prices[i];
                if (price<=leftMin){
                    leftMin = price;
                }else if( (price-leftMin)>maxProfit){
                    maxProfit =price - leftMin;
                }
            }
            return maxProfit;
        }

        public int maxProfitDP(int[] prices) {
            if (prices == null || prices.length < 1) return 0;

            int[][][] t = new int[prices.length][2][2];
            t[0][0][0] = 0;
            t[0][0][1] = Integer.MIN_VALUE; //非法
            t[0][1][0] = 0;
            t[0][1][1] = -prices[0];//买当前

            //k=1 最大1次 ,当卖出时，增1
            for (int i = 1; i < prices.length; i++) {
                t[i][1][0] = Math.max(t[i - 1][1][0], t[i - 1][1][1] + prices[i]);//前一次，没操作，前一次，卖了。
                //t[i][1][1] = Math.max(t[i - 1][1][1], t[i - 1][0][0] - prices[i]);
                //前一次，没操作，当前买了。
                t[i][1][1] = Math.max(t[i - 1][1][1], -prices[i]);// k = 0 时 cur = 0 。 buy , -prices[i]
            }
            return t[prices.length - 1][1][0];
        }

        //最优解 省略 k 因为最大是 1 不需要迭代。
        public int maxProfitDP2(int[] prices) {
//        public int maxProfitPer(int[] prices) {
            if (prices == null || prices.length < 1) return 0;
            int[][] dp = new int[prices.length][2];
            dp[0][0] = 0;
            dp[0][1] = -prices[0];//当天购买了股票。
            for (int i = 1; i < prices.length; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                //dp[i][1] = Math.max(dp[i-1][0] - prices[i],dp[i-1][1]); failed
                dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);//当天购买的 -price[i]. 因为只有 1 次交易的机会。
            }
            return dp[prices.length - 1][0];
        }

        // 空间复杂度优化版本
        //状态转移方程，新状态只和相邻的一个状态有关，其实不用整个dp数组，
        // 只需要一个变量储存相邻的那个状态就足够了，这样可以把空间复杂度降到 O(1):
        int maxProfit(int[] prices) {
            int n = prices.length;
            // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
            int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
                dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
                // dp[i][1] = max(dp[i-1][1], -prices[i])
                dp_i_1 = Math.max(dp_i_1, -prices[i]);
            }
            return dp_i_0;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}